package leetCode;

/**
 915. 分割数组

 给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
 left 中的每个元素都小于或等于 right 中的每个元素。
 left 和 right 都是非空的。
 left 的长度要尽可能小。
 在完成这样的分组后返回 left 的 长度 。
 用例可以保证存在这样的划分方法。

 示例 1：
 输入：nums = [5,0,3,8,6]
 输出：3
 解释：left = [5,0,3]，right = [8,6]

 示例 2：
 输入：nums = [1,1,1,0,6,12]
 输出：4
 解释：left = [1,1,1,0]，right = [6,12]

 提示：
 2 <= nums.length <= 105
 0 <= nums[i] <= 106
 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。
 */
public class PartitionDisjoint {

    public static void main(String[] args) {
        System.out.println(partitionDisjoint(new int[]{1,1}));
    }

    // 动态规划，86/76
    public static int partitionDisjoint(int[] nums) {
        // 假定左侧集合是第一个数
        int leftMax = nums[0];
        int point = 0;
        int curMax = nums[0];
        for (int i = 1;i < nums.length;i++) {
            // 当前的最大数
            curMax = Math.max(curMax, nums[i]);
            // 如果当前数小于左侧最大数，则必须归于左侧，然后断点在当前位置，左侧最大数=至今的最大数，直到右边数都>=左侧数
            if (nums[i] < leftMax) {
                point = i;
                leftMax = curMax;
            }
        }
        return point + 1;
    }
}
